#include <iostream>
#include <map>
#include <vector>

using namespace std;

class Solution {
public:
  int hIndex(vector<int> &citations) {
    // word count: map<references, count>
    // find all reference and count
    // traverse
    //   1. if k <= v => valid, set max val
    //   2. not valid

    // map<k, v>
    // k indice reference count
    // v indice reference bigger than current count indexes

    sort(citations.begin(), citations.end());
    
    map<int, int> cntMap;
    for (int i = 0; i < citations.size(); i++) {

      // less than add
      map<int, int>::iterator it;
      for (it = cntMap.begin(); it != cntMap.end(); it++) {
        if (it->first < citations[i]) {
          it->second++;
        }
      }
      
      // equal add
      map<int, int>::iterator pair = cntMap.find(citations[i]);
      if (pair != cntMap.end()) {
        pair->second++;
      } else {
        cntMap.insert(make_pair(citations[i], 1));
      }
    }

    int maxVal = 0;
    map<int, int>::iterator it;
    for (it = cntMap.begin(); it != cntMap.end(); it++) {
      //cout << "cur, first: " << it->first << "second: " << it->second << endl;
      int curMin = it->first;
      if (it->second < it->first) {
        curMin = it->second;
      }
      if (curMin > maxVal) {
        maxVal = curMin;
      }
    }

    return maxVal;
  }
};

int main() {

  vector<int> vec;
  // vec.push_back(3);
  // vec.push_back(0);
  // vec.push_back(6);
  // vec.push_back(1);
  // vec.push_back(5);
  
  vec.push_back(0);
  vec.push_back(3);
  vec.push_back(2);
  vec.push_back(0);

  Solution so;
  int ret = 0;
  ret = so.hIndex(vec);

  cout << "ret:" << ret << endl;
  return 0;
}
